//
// Created by mac on 1/29/22.
//


#include <vector>
#include <iostream>
using namespace std;

void merge(vector<int> &nums, int start, int end, int mid, vector<int>&temp){
    if(start>=end){
        return;
    }

    int i_start = start;
    int i_end = mid;
    int j_start = mid+1;
    int j_end = end;
    //辅助空间
    int length = 0;


    while (i_start<=i_end && j_start<=j_end){
        if(nums[i_start]<= nums[j_start]){
            temp[length] = nums[i_start];
            length++;
            i_start++;
        }else{
            temp[length] = nums[j_start];
            j_start++;
            length++;
        }
    }

    while (i_start<=i_end){
        temp[length] = nums[i_start];
        i_start++;
        length++;
    }

    while (j_start<=j_end){
        temp[length] = nums[j_start];
        j_start++;
        length++;
    }

    // 辅助空间放到原来空间
    for (int i = 0; i < length; ++i) {
        nums[start+i] = temp[i];
    }

}

void mergeSort(vector<int> &nums, int start, int end, vector<int>&temp){
    if(start>=end){
        return;
    }
    //中间值
    int mid = start+(end-start)/2;
    //左半边
    mergeSort(nums, start, mid, temp);

    //右半边
    mergeSort(nums, mid+1, end, temp);

    merge(nums, start, end, mid, temp);
}

int main() {

    vector<int> num = {2, 6, 2, 5, 1, 8, 32, 22, 7};

    vector<int> temp(num.size());

    mergeSort(num, 0, num.size()-1, temp);
    for(int n:num){
        cout<<n<<endl;
    }
    return 0;
}